package com.hy.study.sort;

import java.util.Arrays;

/**
 * shellSort
 */
public class ShellSort {
    public static void main(String[] args) {
        //int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        // int arr[] = new int[80000];
        int arr[] = {12, 34, -2, 3, 22, 9, 0};
        for (int i = 0; i < arr.length; i++) {
            //arr[i] = (int) (Math.random() * 800000);
        }
        System.out.println("----------排序前----------");
        System.out.println(Arrays.toString(arr));
        long startTime = System.currentTimeMillis();
        shellSort(arr);//交换式
        //shellSort2(arr);//移位式
        long endTime = System.currentTimeMillis();
        System.out.println("----------排序后----------");
        System.out.println(Arrays.toString(arr));
        System.out.println("---------总共耗时(" + (endTime - startTime) / 1000 + "秒)");
    }


    /**
     * 交换希尔排序
     *
     * @param arr
     */
    private static void shellSort(int arr[]) {
        int temp = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //第一轮将10个数分成5组
            for (int i = gap; i < arr.length; i++) {
                //遍历各个组中的元素(共5组，每组2个元素) 元素与元素之间相隔5个长度
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }

    }

    /**
     * 移位希尔排序
     *
     * @param arr
     */
    public static void shellSort2(int arr[]) {

        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[i];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出循环时 移动位置
                    arr[j] = temp;
                }
            }
        }
    }
}
